package cn.edu.jxau.test;

public class Main {

    public static void main(String[] args) {

        DynamicMedian dm = new DynamicMedian();
        dm.insert(10);
        dm.insert(20);
        dm.insert(20);
        dm.insert(20);
        dm.insert(30);
        dm.insert(20);
        System.out.println(dm.median());
        dm.delMedian();
        System.out.println(dm.median());
        dm.delMedian();
        System.out.println(dm.median());
    }
}

/**
 * 动态查找中位数
 * 
 * @author 付大石
 */
class DynamicMedian {

    private MaxPQ maxPQ; // 存储较小的一部分
    private MinPQ minPQ; // 存储较大的一部分

    private static final int INIT_CAPACITY = 20;

    public DynamicMedian() {
        maxPQ = new MaxPQ(INIT_CAPACITY);
        minPQ = new MinPQ(INIT_CAPACITY);
    }

    /**
     * 插入一个数值
     * 
     * @param i
     */
    public void insert(int i) {

        if (maxPQ.isEmpty()) { // 初始是maxPQ为空，优先插入maxPQ中
            maxPQ.insert(i);
            return ;
        }
        if (i < maxPQ.max()) {
            maxPQ.insert(i);
        } else {
            minPQ.insert(i);
        }
        if (maxPQ.size() - minPQ.size() > 1) { // maxPQ过大
            minPQ.insert(maxPQ.delMax());
        } else if (minPQ.size() - maxPQ.size() > 1) { // minPQ过大
            maxPQ.insert(minPQ.delMin());
        }
    }

    /**
     * 获取当前的中位数
     */
    public int median() {
        return maxPQ.max();
    }

    /**
     * 获取当删除当前中位数
     */
    public int delMedian() {
        
        int median = maxPQ.delMax();
        if(minPQ.size()>maxPQ.size()) {
            maxPQ.insert(minPQ.delMin());
        }
        return median;
    }
}
